package club.banyuan;

import java.util.Arrays;

public class MyArrayList<E extends Comparable<E>> {

  private Object[] data; // 用来存放数据 - 列表中的元素
  private int size; // 表示当前内部数组的容量
  private int curr; // 用来指示当前存放了多少个元素在数组里面

  public MyArrayList() {
    size = 8;
    curr = 0;
    data = new Object[size];
  }

  /**
   * @param e - 添加到list中的元素
   * @param pos - 添加到哪个位置
   * @return - 成功/失败
   */
  public boolean add(E e, int pos) {
    // 考虑pos的有效范围 [0, curr]
    // [1, 2, 3] (5, ?)
    if (pos < 0 || pos > curr) {
      // 增加元素的位置不正确， 返回失败
      return false;
    }
    // [a, b, c] (d, 1) -> [a, d, b, c]
    if (curr == size) {
      // 当前的内部数组已经满了
      data = Arrays.copyOf(data, size * 2);
      size = size * 2;
    }
    // 将pos开始的元素依次往后移动一个位置
    // [a, b, c] -> [a,  , b, c]
    for (int i = curr - 1; i >= pos; i--) {
      data[i + 1] = data[i];
    }
    // System.arraycopy(data, pos, data, pos + 1, curr - pos);
    data[pos] = e;
    curr++;
    return true;
  }

  public boolean addAtHead(E e) {
    return add(e, 0);
  }

  public boolean addAtTail(E e) {
    return add(e, curr);
  }

  // TODO 作业： 在main方法中测试get方法是否正常工作
  @SuppressWarnings("unchecked")
  public E get(int pos) {
    if (pos < 0 || pos >= curr) {
      return null;
    } else {
      return (E) data[pos];
    }
  }

  // TODO 作业： 增加删除第0个元素和删除最后一个元素的方法
  @SuppressWarnings("unchecked")
  public E remove(int pos) {
    if (pos < 0 || pos >= curr) {
      return null;
    } else {
      // 删除pos位置的元素
      var r = data[pos];
      //      E r = data[pos];
      // 从pos+1开始到curr结束的元素都向左边移动一个位置， 不包含curr
      // [1, 2, 3] 删除pos为1的元素
      // curr = 3， pos = 1, 实际拷贝了1个元素 1 = curr - 1 - pos
      System.arraycopy(data, pos + 1, data, pos, curr - 1 - pos);
      curr--;
      return (E) r;
    }
  }

  @Override
  // TODO 作业： 修正下面的toString方法，最后一个元素后面不能出现逗号和空格
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append(this.getClass().getName());
    builder.append(": [");
    for (int i = 0; i < curr; i++) {
      builder.append(data[i].toString());
      builder.append(", ");
    }
    builder.append("]");
    return builder.toString();
  }

  // 返回当前内部数组中包含了多少个元素
  public int size() {
    return curr;
  }

  /** search， 查找列表里对应元素的位置 */
  // TODO 作业：完成search方法
  public int search(E e) {
    return 0;
  }

  /**
   * 获取当前列表中最大的元素
   *
   * @return 最大元素
   */
  @SuppressWarnings("unchecked")
  public E getMax() {
    if (curr == 0) return null;
    E max = (E) data[0];
    for (int i = 1; i < curr; i++) {
      if (((E) data[i]).compareTo(max) > 0) max = (E) data[i];
    }
    return max;
  }

  /**
   * 交换数组中的两个位置
   *
   * @param i - 元素1的下标
   * @param j - 元素2的下标
   */
  private void swap(int i, int j) {
    var temp = data[i];
    data[i] = data[j];
    data[j] = temp;
  }

  /**
   * 将当前数组进行插入排序
   *
   * <p>每次选择一个未排序的元素， 将其放到左边已排序的合适位置
   */
  @SuppressWarnings("unchecked")
  public void insertionSort() {
    for (int i = 1; i < curr; i++) {
      int j = i;
      while (j > 0 && ((E) data[j]).compareTo((E) data[j - 1]) < 0) {
        // 交换j和j-1
        swap(j, j - 1);
        j--;
      }
    }
  }

  /**
   * 选择排序
   *
   * <p>每次从未排序的数组中选择一个最小的元素，和第一个元素进行交换
   */
  @SuppressWarnings("unchecked")
  public void selectionSort() {
    // i 表示未排序的元素开始的位置
    for (int i = 0; i < curr - 1; i++) {
      // 从i到curr-1中选择一个最小的元素，和i交换
      int minIndex = i;
      for (int j = i + 1; j < curr; j++) {
        if (((E) data[j]).compareTo((E) data[minIndex]) < 0) minIndex = j;
      }
      if (minIndex != i) swap(i, minIndex);
    }
  }

  /**
   * 冒泡排序
   *
   * <p>每轮冒泡，左右两个元素比较，如果左边大于右边， 则交换位置，
   *
   * <p>得大的元素冒泡到最右边
   */
  @SuppressWarnings("unchecked")
  public void bubbleSort() {
    // i表示从什么地方开始冒泡
    for (int i = 0; i < curr - 1; i++) {
      // j 表示每轮冒泡的下标

      // 优化：如果一轮冒泡一次交换都没有发生，表示当前数组已经是有序数组
      boolean sorted = true;
      for (int j = 0; j < curr - 1 - i; j++) {
        // 如果 j > j+1, 则交换
        if (((E) data[j]).compareTo((E) data[j + 1]) > 0) {
          swap(j, j + 1);
          sorted = false;
        }
      }
      if (sorted) break;
    }
  }

  @SuppressWarnings("unchecked")
  void innerQuickSort(Object[] a, int begin, int end) {
    // 只有1个元素或没有元素， 不需要进行排序
    // 递归的出口条件
    if (begin >= end - 1) return;
    // 多余一个元素
    // 通过a[begin]作为标杆， 将[begin+1, end)的元素分成两部分
    // i 从begin +1开始， j从end-1开始，
    int i = begin + 1;
    int j = end - 1;

    // 找到一个i使得 a[i] >= a[begin]，以及一个j 使得 a[j] < a[begin]
    // 交换i和j.... 直到j < i
    // 再交换j和begin, 此时j已经处于合适的位置，
    // 再对[begin, j) 和 [j+1, end)进行排序

    while (i <= j) {
      // 找到一个i和j
      while (i < end && ((E) a[i]).compareTo(((E) a[begin])) < 0) i++;
      while (j >= i && ((E) a[j]).compareTo(((E) a[begin])) >= 0) j--;
      if (i < j) {
        swap(i, j);
        i++;
        j--;
      }
    }
    if (j != begin)
      swap(j, begin);
    innerQuickSort(a, begin, j);
    innerQuickSort(a, j + 1, end);
  }

  /**
   * 快速排序
   *
   * <p>选取一个标杆， 将现有数组分成两部分，
   *
   * <p>左边的小于等于标杆， 右边的大于标杆
   *
   * <p>在分别对左右进行排序
   */
  void quickSort() {
    // data 0 -> curr -1
    innerQuickSort(data, 0, curr);
  }

  /**
   * @param a   - 待搜索的数组
   * @param min - 数组最小下标， 包含
   * @param max - 数组最大下标， 不包含
   * @param e   - 匹配的元素
   * @return - e在数组中的下标， 找不到则返回-1
   */
  @SuppressWarnings("unchecked")
  private int innerBinarySearch(Object[] a, int min, int max, E e) {
    // min - 0, max - 1
    if (min >= max) {
      return -1;
    }

    int mid = (min + max) >> 1;
    // min = 0
    if (((E) a[mid]).compareTo(e) > 0) return innerBinarySearch(a, min, mid, e);
    else if (((E) a[mid]).compareTo(e) < 0) return innerBinarySearch(a, mid + 1, max, e);
    else return mid;
  }

  /**
   * 二分搜索 - 在有序数组中使用
   *
   * @param e - 要找的元素
   * @return - 该元素在数组中的下标， 如果没有这个元素， 则返回 -1
   */
  public int binarySearch(E e) {
    return innerBinarySearch(data, 0, curr, e);
  }
}
